/**
 * 仿射密码
 */
public class AffineCipher {
    int a0=1, a1=1, b0=3, m0=26;
    boolean isA1;
    //构造函数，3个参数分别是密钥a,b,m
    public AffineCipher(int a, int b, int m){
        setKey(a, b, m);
    }
    public void setKey(int a, int b, int m){
        this.a0 = a;
        this.b0 = b;
        this.m0 = m;
        isA1 = gcd(a0, m0) == 1;
        if(isA1){
            a1 = getInverseByExgcd(a0, m0);
        }
        else{
            System.out.println("a和m不互质，不存在逆元");
        }
    }
    //欧几里得算法计算最大公约数
    int gcd(int a, int b){
        int x = Math.max(a, b);
        int y = Math.min(a, b);
        while(y!=0){
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }
    //欧几里得扩展算法计算逆元
    int [] exgcd(int a, int b){
        if(b == 0){
            return new int[]{a, 1, 0};
        }
        int [] res = exgcd(b , a % b);
        int x = res[2];
        int y  = res[1] - (a/b)*res[2];
        return new int[]{res[0], x, y};
    }

    // 扩展欧几里得算法求逆元
    int getInverseByExgcd(int a, int m){
        int [] res = exgcd(a, m);
        int gcd = res[0];
        if(gcd!=1){
            throw new IllegalArgumentException("a and m are not coprime");
        }
        return ((res[1]%m)+m)%m;
    }

    public int encrypt(int input){
        int output = (a0 * input + b0) % m0;
        return ((output%26)+26)%26;
    }

    public int decrypt(int input) {
        int output = a1 * (input - b0) % m0;
        return ((output%26)+26)%26;
    }

    public String encrypt(String input){
        if(isA1) {
            StringBuilder output = new StringBuilder();
            //遍历明文字符串的每个字符
            for (char m : input.toCharArray()) {
                //判断是否是大写字母
                if (Character.isUpperCase(m)) {
                    //把大写字母A-Z转为数字0-25
                    int m_int = m - 65;
                    //执行公式 C = (M + K) MOD 26
                    int c_int = encrypt(m_int);
                    //把数字0-25转为密文字母A-Z
                    char c = (char) (c_int + 65);
                    //把密文字符添加到字符串output中
                    output.append(c);
                    //判断是否小写字母
                } else if (Character.isLowerCase(m)) {
                    //把小写字母a-z转为数字0-25
                    int m_int = m - 97;
                    //执行公式 C = (M + K) MOD 26
                    int c_int = encrypt(m_int);
                    //把数字0-25转为密文字母a-z
                    char c = (char) (c_int + 97);
                    //把密文字符添加到字符串output中
                    output.append(c);
                } else {
                    //如果不是字母，则不做加密解密
                    output.append(m);
                }
            }
            return output.toString();
        }else{
            System.out.println("a和m不互质，不存在逆元");
            return null;
        }
    }
    public String decrypt(String input){
        if(isA1) {
            StringBuilder output = new StringBuilder();
            //遍历明文字符串的每个字符
            for (char c : input.toCharArray()) {
                //判断是否是大写字母
                if (Character.isUpperCase(c)) {
                    //把大写字母A-Z转为数字0-25
                    int c_int = c - 65;
                    //执行公式 C = (M + K) MOD 26
                    int m_int = decrypt(c_int);
                    //把数字0-25转为密文字母A-Z
                    char m = (char) (m_int + 65);
                    //把密文字符添加到字符串output中
                    output.append(m);
                    //判断是否小写字母
                } else if (Character.isLowerCase(c)) {
                    //把小写字母a-z转为数字0-25
                    int c_int = c - 97;
                    //执行公式 C = (M + K) MOD 26
                    int m_int = decrypt(c_int);
                    //把数字0-25转为密文字母a-z
                    char m = (char) (m_int + 97);
                    //把密文字符添加到字符串output中
                    output.append(m);
                } else {
                    //如果不是字母，则不做加密解密
                    output.append(c);
                }
            }
            return output.toString();
        }else{
            System.out.println("a和m不互质，不存在逆元");
            return null;
        }
    }
    public static void main(String[] args) {
        AffineCipher affineCipher = new AffineCipher(19, 23, 26);
        String t = "affineisinteresting";
    }
}
